Generating Random Elements of Finite Distributive Lattices

摘要

This survey article describes a method for choosing uniformly at random fromany finite set whose objects can be viewed as constituting a distributivelattice. The method is based on ideas of the author and David Wilson for using``coupling from the past'' to remove initialization bias from Monte Carlorandomization. The article describes several applications to specific kinds ofcombinatorial objects such as tilings, constrained lattice paths, andalternating-sign matrices.